The present invention relates to the field of raster shape synthesis, i.e., the creation of shapes for display on a raster display device. More specifically, in one embodiment of the invention, multi-level raster shapes are synthesized efficiently.
A raster display device comprises a rectangular array of uniformly spaced picture elements, or pixels. A pixel is the smallest independent element of the raster device which can be addressed and each pixel can be made to take on a color selected from a range of colors which are displayable by the device. A raster device can display an image of virtually any two-dimensional shape, by coloring a group of pixels so as to collectively suggest the desired shape. It is this flexibility, that any device can represent any shape, which has made raster devices the preferred output devices for today's computers and many consumer products. Dot matrix printers, laser printers, facsimile machines, video game displays, high-definition televisions, and computer monitors are all examples of raster display devices.
A raster shape is an entity that can be used to display a shape on a raster device by specifying which pixels to use to produce its likeness. For example, the shape may be a character taken from a font at a given point size, and the raster shape would tell which group of pixels could be used to produce a rendition of the character. Because pixels of real raster devices have finite size, a raster shape is necessarily finite and discrete and therefore can only approximate many common shapes which are continuous. This is the case even when the shape can be described succinctly with arbitrary precision. For example, a circle is precisely described by its center and its radius, however any group of pixels used to display that circle cannot perfectly represent the circle. Thus, a raster shape is only a representation of an ideal shape. The raster shape synthesis task comprises the computation of a raster shape which approximately represents a continuous, arbitrarily precise, description of a shape.
Typically, a raster shape is a rectangular array of "coverage" values corresponding to a portion of the array of pixels of a raster device. Each pixel in the array is assigned a coverage value which indicates whether the pixel is part of the raster shape or not. By convention, pixels that are part of the shape ("inside pixels") are assigned an coverage value of 1 and those pixels that are not part of the shape ("outside pixels") are assigned a value of 0. In some raster shapes, certain pixels ("boundary pixels") may be given fractional coverage values between 0 and 1. In order not to have to compute or store more coverage values than necessary, it is customarily assumed that pixels not explicitly assigned a coverage value are outside the shape, that is, they have a coverage value of 0.
The simplest raster shapes are bi-level representations of an ideal shape, where all the pixels have coverage values of either 0 or 1, that is, each pixel is designated as being either an inside pixel or an outside pixel. Multi-level raster shapes may, in contrast, include pixels with coverage values between 0 and 1 to capture the fact that an ideal shape may be approximated more precisely if certain pixels are allowed to be part inside pixel and part outside pixel. Herein, such pixels will be termed "boundary pixels". Typically, the coverage values used in a multi-level raster shape are not real numbers with arbitrary precision but rather numbers taken from a finite set of levels, such as 0, 1/4 and 1. In principle, the higher the number of levels, the more precisely a multi-level raster shape can approximate an ideal shape. In practice, however, using more than roughly 16 levels produces only marginal improvements, when the measure of improvement is the visual perception of the shape by a person viewing the raster shape.
A multi-level raster shape contains more information than a bi-level raster shape with the same number of pixels. Some raster devices may be capable of using the additional nformation to improve the appearance of the raster shapes displayed. The improvement is more marked when the number of pixels used to represent the ideal shape is small. As the number of pixels grows, the raster shape more closely approximates the ideal shape, and the differences between bi-level and multi-level raster shapes at a given resolution become less and less noticeable. Multi-level raster shapes are therefore particularly useful to depict small objects on raster display devices which have a low resolution. One common example of these circumstances is the display of character shapes on computer screens, and for this task multi-level raster shapes offer notable improvements over the bi-level raster shapes in common use today.
A raster shape does not specify color. For example, a bi-level raster shape for a circle can be used equally well to display a black circle or a red circle, by making the pixels inside the raster shape black or red and leaving those outside the raster shape unchanged. The partial coverage values in a multi-level raster shape are also devoid of color. When displaying a shape, the intermediate coverage value of a boundary pixel is interpreted as an indication that the color of the pixel should be computed by an interpolation of the color of the shape and the color of the background, with higher coverage values indicating a higher proportion of the shape color in the mixture. The mixed colors thus obtained smooth the transition between the inside and the outside of the shape and improve its appearance. The need to blend the shape and background colors restricts the use of multi-level raster shapes to raster devices capable of displaying a large number of colors or shades of one color. Commonly used raster shapes, particularly characters, are very often drawn in black over a white background; in that case multi-level raster shapes produce gray shades (mixtures of black and white) around the edge of the shape. For this reason, multi-level raster shapes are often called "gray-level". The term "gray-level" is avoided herein, as it is misleading because it implies an nonexistent association between the raster shape and the colors produced when using the raster shape.